package main

import (
	"fmt"
)

//1,9,2,8,3,   7,4,6,5,10
//1,9,2,   8,3,        7,4,6,5,10
//1,2,   9,
//3,8
//1  2  3  8  9     //  456 7 10

//归并排序
func merge(leftArr []int, rightArr []int) []int {
	leftIndex := 0
	rightIndex := 0
	lastArr := []int{} //返回最后数组
	for leftIndex < len(leftArr) && rightIndex < len(rightArr) {
		if leftArr[leftIndex] > rightArr[rightIndex] { //大于
			lastArr = append(lastArr, rightArr[rightIndex])
			rightIndex++
		} else if leftArr[leftIndex] < rightArr[rightIndex] { //小于
			lastArr = append(lastArr, leftArr[leftIndex])
			leftIndex++
		} else { //等于
			lastArr = append(lastArr, leftArr[leftIndex])
			leftIndex++

			lastArr = append(lastArr, rightArr[rightIndex])
			rightIndex++
		}
	}

	if leftIndex < len(leftArr) { //没有对比完的数据加到后面
		lastArr = append(lastArr, leftArr[leftIndex:]...)
	}

	if rightIndex < len(rightArr) { //没有对比完的数据加到后面
		lastArr = append(lastArr, rightArr[rightIndex:]...)
	}

	return lastArr
}

// 分解数组
func MergeSort(arr []int) []int {
	length := len(arr)
	if length <= 1 {
		return arr
	} else { //可以将大于2和小于10的数组。用选择排序和插入排序
		mid := length / 2

		leftArr := MergeSort(arr[:mid])
		rightArr := MergeSort(arr[mid:])

		fmt.Println(leftArr)
		fmt.Println(rightArr)

		return merge(leftArr, rightArr)
	}
}

func main() {
	arr := []int{3, 59, 4, 2, 9, 6, 78, 13, 9, 18, 16, 28, 22}

	fmt.Println(arr)

	fmt.Println(MergeSort(arr))

}
